package nowcoder.offer;

import java.util.ArrayList;

/**
 * 滑动窗口的最大值
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-30 14:48
 */
public class MaxInWindows {

    public ArrayList<Integer> solution(int[] num,int size){
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || num.length == 0 || size == 0 || size > num.length) return res;

        int maxIndex = max(num,0,size-1);
        res.add(num[maxIndex]);
        int len = num.length;

        for (int i = size; i < len; i++) {
            if (i -size +1 > maxIndex){
                maxIndex = max(num,i-size+1,i);
                res.add(num[maxIndex]);
                continue;
            }

            if (num[i] > num[maxIndex]){
                maxIndex = i;
                res.add(num[maxIndex]);
                continue;
            }

            res.add(num[maxIndex]);
        }

        return res;
    }

    public int max(int[] array,int start,int end){
        int maxIndex = start;
        for (int i = start+1; i <= end; i++) {
            if (array[i] > array[maxIndex])
                maxIndex = i;
        }

        return maxIndex;
    }

    public static void main(String[] args) {
        int[] array = {2, 3, 4, 2, 6, 2, 5, 1};
        new MaxInWindows().solution(array,3);
    }
}
